package org.example.GC;

import java.util.Stack;

public class lands {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    count++;
                    dfs(grid, i, j);
                }
            }
        }
        return count;
    }

    private void dfs(char[][] grid, int i, int j) {

        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0') {
            return;
        }
        grid[i][j] = '0';
        dfs(grid, (i - 1), j);
        dfs(grid, (i + 1), j);
        dfs(grid, i, (j - 1));
        dfs(grid, i, (j + 1));
    }

    public String decodeString(String s) {
        Stack<StringBuilder> stringBuilderStack = new Stack<>();
        Stack<Integer> integerStack = new Stack<>();
        char[] chars = s.toCharArray();
        StringBuilder stringBuilder = new StringBuilder();
        int nums = 0;
        for (char c : chars) {
            if (Character.isDigit(c)) {
                nums = nums * 10 + (c - '0');
            } else if (c == '[') {
                stringBuilderStack.push(stringBuilder);
                integerStack.push(nums);
                stringBuilder = new StringBuilder();
                nums = 0;
            } else if (c == ']') {
                StringBuilder stringBuilder1 = stringBuilderStack.pop();
                int n = integerStack.pop();
                for (int k = 0; k < n; k++) {
                    stringBuilder1.append(stringBuilder);
                }
                stringBuilder = stringBuilder1;
            } else {
                stringBuilder.append(c);
            }
        }
        return stringBuilder.toString();
    }

    public int pivotIndex(int[] nums) {
        int sum1 = 0;
        int sum2 = 0;
        int i ;
        for (i = 0; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                sum1 = sum1 + nums[j];
            }
            for (int k = nums.length - 1; k > i; k--) {
                sum2 = sum2 + nums[k];
            }
            if (sum1 == sum2) {
                return i;
            }else {
                sum1=0;
                sum2=0;
            }
        }
        return -1;
    }

    public int searchInsert(int[] nums, int target) {
        int a= nums.length;
        for (int i =0;i<nums.length;i++){
            if (target>nums[nums.length-1]){
                return nums.length;
            }else if (target<=nums[i]){
                return i;
            }
        }
        return a;
    }

}
